package leetcode.editor.cn;
 
/**
 * 组合总和 Ⅳ
 * @author qulq
 * @date 2024-07-25 21:28:53
 */
public class T377_CombinationSumIv{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T377_CombinationSumIv().new Solution();
	 }

	/**
	 * 完全背包，求排列，背包在外层、物品在内层
	 * dp[j] ：下标0-i，凑成容量j的种数
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int combinationSum4(int[] nums, int target) {
		int[] dp = new int[target + 1];
		dp[0] = 1;
		for (int i = 1; i <= target; i++) {
			for (int j = 0; j < nums.length; j++) {
				if (i >= nums[j]) {
					dp[i] += dp[i - nums[j]];
				}
			}
		}
		return dp[target];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}